6.824 Lab3A

6.824 Lab 3A

摘要

Lab3 要求完成基于raft的可容错Key-Value存储。Lab3分成Lab3A和Lab3B，3A要求实现简单的将每个请求的内容追加到 log 列表中，而不用考虑他的空间占用。Lab3B要求实现Snapshot。

感想

完全理解Key-Value Storage和Raft的关系非常重要，如果不能完全理解那么在实现的过程中会遇到很多问题。Raft是一个duplicate state machine，通过维护一份共同的log来防止少于半数的服务器出错（网络、宕机）带来的错误。这次的Key-Value Storage是建立在Raft协议之上的一个存储系统，也就是分布式可容错存储。

结构

通过调用在Lab2中实现的Raft Library，来得到一致的Log，只要Log是一致的，那么最终得到的结果就是一致的。于是就有了思路，不管是Put、Append还是Get，只要全部丢进raft log，然后再根据raft log来返回结果。结合Lab3A的实验文档，大致可以得出这样的结构。

graph LR A["Clerk"] B["KVServer(raft leader)"] C["KVServer(raft peer)"] D["KVServer(raft peer)"] E["KVServer(raft peer)"] F["KVServer(raft peer)"] A -- put/append/get --> B B -- log replication--> C B -- apply -->B C -- apply -->C D -- apply -->D E -- apply -->E F -- apply -->F B -- log replication--> D B -- log replication--> E B -- log replication--> F B -- when applied --> A

还记得在Lab2中，为election timeout和commit applier单独开一个后台线程，那么在Lab3A中，为每个KVServer开一个后台线程接收applymsg通道中的内容，注意applymsg是一个阻塞的通道，必须要及时取出，否则raft无法继续commit log。

返回请求

所有的KVServer都护拥有一份一致的Log，但是只有Leader才会被Clerk请求，所以Leader不仅仅要Apply指令，还要返回处理的结果。那么方法就是为每一个指令开一个通道，KVServer向Raft使用Start()提交指令会阻塞等待通道返回结果，同时Applier的后台线程在处理完成/发现重复后向这个通道发送处理结果。

这里会遇到一个问题，假如Raft长时间没有完成Log Replication或者Raft leader被替换了，这时这个通道就有可能永远不会有结果，那么Clerk那边就会陷入无限等待，于是给一个Timeout，我这里设置为2000毫秒。假如这个Timeout过短，那么及时Raft正常完成复制，也可能遇到Timeout的情况，这样Clerk最终还是re-send给这个Leader，这个Leader会提交，然后在apply时发现已经处理过了。

重复提交

当网络出现问题，或者服务器宕机时，会发生Clerk多次提交同一请求的情况，处理办法就是为每一个请求生成一个唯一的id，这个id由Clerk id和他的Request id组成，每个id都是单调增加的，然后在apply时标记这次处理的command的id，然后跳过已经处理过的command。

type identifier struct {
    Id      int
    Index   int
}

持久化

raft的log是持久化的，利用这个特点，就可以通过log还原出data的情况，在重启后执行即可。

实验结果

$ go test -run 3A
Test: one client (3A) ...
labgob warning: Decoding into a non-default variable/field Index may not work
  ... Passed --  15.5  5  1421  142
Test: many clients (3A) ...
  ... Passed --  16.9  5  1904  506
Test: unreliable net, many clients (3A) ...
  ... Passed --  17.0  5  2271  376
Test: concurrent append to same key, unreliable (3A) ...
  ... Passed --   5.2  3   396   52
Test: progress in majority (3A) ...
  ... Passed --   0.4  5    65    2
Test: no progress in minority (3A) ...
  ... Passed --   1.3  5   223    3
Test: completion after heal (3A) ...
  ... Passed --   1.1  5    97    3
Test: partitions, one client (3A) ...
  ... Passed --  22.8  5  2614   78
Test: partitions, many clients (3A) ...
  ... Passed --  23.7  5  5189  330
Test: restarts, one client (3A) ...
  ... Passed --  19.4  5  1704  142
Test: restarts, many clients (3A) ...
  ... Passed --  22.9  5  3387  512
Test: unreliable net, restarts, many clients (3A) ...
  ... Passed --  25.8  5  3193  368
Test: restarts, partitions, many clients (3A) ...
  ... Passed --  27.7  5  4815  331
Test: unreliable net, restarts, partitions, many clients (3A) ...
  ... Passed --  28.3  5  3723  180
Test: unreliable net, restarts, partitions, many clients, linearizability checks (3A) ...
  ... Passed --  29.4  7 11837  161
PASS
ok      kvraft  258.530s

时间

写于2019年11月9日